package cn.lishiyuan.algorithm.list;

import java.util.Objects;


/**
 * 单循环链表
 * @param <T>
 */
public class SingleCycleLinkedList<T> implements LeeList<T>,Josephus<T>{

    private Node<T> head = null;
    private Node<T> tail = null;

    private int size = 0;

    public static class Node<T>{
        T data;
        Node<T> next = null;
    }

    public SingleCycleLinkedList(){}


    public SingleCycleLinkedList(T data){
        Node<T> newNode = newNode(data);
        head = newNode;
        tail = newNode;
        tail.next = head;
        size = 1;
    }

    @Override
    public void addFirst(T data){
        Node<T> node = newNode(data);

        if (isEmpty()) {
            head = node;
            tail = node;
            tail.next = head;
        }else {
            // 本节点的后继是之前的头节点
            node.next = head;
            tail.next = node;
            // 本节点是新的头节点
            head = node;
        }

        size++;
    }

    @Override
    public void addLast(T data){
        Node<T> node = newNode(data);
        if(isEmpty()) {
            // 本节点是第一个节点
            head = node;
            tail = node;
            tail.next = head;
        }else {
            // 获取最后一个节点
            tail.next = node;
            node.next = head;
            tail = node;
        }

        size++;
    }

    @Override
    public void add(int index, T data){
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        // 第一个元素
        if(index == 0){
            addFirst(data);
            return;
        }
        // 最后一个元素
        if(index == size){
            addLast(data);
            return;
        }

        Node<T> newNode = newNode(data);
        // 该位置的前一个节点
        Node<T> preNode = findNode(index-1);

        if(Objects.isNull(preNode)){
            throw new IllegalStateException("数据异常");
        }

        // 该位置的当前节点
        Node<T> nextNode = preNode.next;

        // 前一个节点的后继设置为新节点
        preNode.next = newNode;
        // 新节点的后一个节点是当前节点
        newNode.next = nextNode;
        size++;
    }

    @Override
    public T removeFirst(){
        if(isEmpty()){
            return null;
        }

        if(size == 1){
            T data = head.data;
            head = null;
            tail = null;
            size = 0;
            return data;
        }

        Node<T> node = head;
        T data = node.data;
        head = node.next;
        tail.next = head;

        node.next = null;

        size--;
        return data;
    }

    @Override
    public T removeLast(){
        if(isEmpty()){
            return null;
        }
        if(size == 1){
            // 只有一个节点也就是头节点
            return removeFirst();
        }
        // 此时最少有两个节点

        Node<T> preNode = findNode(size - 2);

        if(Objects.isNull(preNode)){
            throw new IllegalStateException("数据异常");
        }

        // 最后一个节点
        Node<T> node = preNode.next;

        preNode.next = node.next;
        tail = preNode;
        node.next = null;

        size --;
        return node.data;
    }

    @Override
    public T remove(int index){
        if(isEmpty()){
            return null;
        }
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }

        if(index == 0){
            // 只有一个节点也就是头节点
            return removeFirst();
        }

        if(index == (size - 1) ){
            return removeLast();
        }
        // 此时最少有两个节点

        // 最后一个节点的前节点
        Node<T> preNode = findNode(index - 1);
        if(Objects.isNull(preNode)){
            throw new IllegalStateException("数据异常");
        }
        // 最后一个节点
        Node<T> node = preNode.next;

        preNode.next = node.next;
        node.next = null;

        size --;
        return node.data;
    }

    @Override
    public T get(int index){
        Node<T> node = findNode(index);
        if(Objects.isNull(node)){
            return null;
        }else {
            return node.data;
        }
    }

    @Override
    public int indexOf(T data){
        int nowIndex = 0;
        // 查找某个index的元素
        for(Node<T> cur = head;  nowIndex < size; cur = cur.next , nowIndex ++){
            // 查找某个data的元素
            if(Objects.equals(data, cur.data)){
                return nowIndex;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(Object data){
        Node<T> node = findNode(data);
        return Objects.nonNull(node);
    }


    private Node<T> findNode(int index){
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        if(index == 0){
            return head;
        }

        int nowIndex = 0;
        // 查找某个index的元素
        for(Node<T> cur = head; nowIndex < size; cur = cur.next){
            if(index == nowIndex){
                return cur;
            }else {
                nowIndex++;
            }
        }

        return null;
    }


    private Node<T> findNode(Object data){
        int nowIndex = 0;

        // 查找某个index的元素
        for(Node<T> cur = head; cur != null &&  nowIndex < size; cur = cur.next ,nowIndex++){
            // 查找某个data的元素
            if(Objects.equals(data, cur.data)){
                return cur;
            }
        }

        return null;
    }


    // 构建节点
    private Node<T> newNode(T data){
        Node<T> node = new Node<>();
        node.data = data;
        return node;
    }


    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return head == null;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();

        builder.append("size = ").append(size).append("; list = ");
        builder.append("[");

        Node<T> cur = head;

        for( int nowIndex = 0; cur != null &&  nowIndex < size;  nowIndex ++){
            builder.append(cur.data);
            cur = cur.next;
            if(cur != null){
                builder.append(",");
            }
        }


        builder.append("]");
        return builder.toString();
    }

    @Override
    public T josephus(int step) {
        if(step <= 0){
            throw new IllegalArgumentException("step <= 0");
        }

        if(isEmpty()){
            return null;
        }

        if(step == 1){
            tail.next = tail;
            head = tail;
            return tail.data;
        }
        // 从 -1 index开数
        // 比如 [1,2,3],要从尾部开始走第一步
        Node<T> cur = tail;

        // 非唯一节点
        while (cur != cur.next){
            // 比如你要走三步，那你应该在第二步停下
            for(int index = 0; index < (step - 1); index++){
                // 走n步
                cur = cur.next;
            }
            // 需要删除的节点
            Node<T> node = cur.next;
            // 删除当前节点
            cur.next = cur.next.next;
            // 处理head和tail
            // 如果node是head节点，则设置head为下一个节点
            if(node == head){
                head = cur.next;
            }
            // tail是当前节点的上个节点
            if(node == tail){
                tail = cur;
            }
            size--;
        }

        return cur.data;
    }



}
